﻿
//{{{ file documentation -------------------------------------------------------

/*!
 * @file     ortho.cpp
 * @brief    dicodor "orthographe" class implementation
 */

//}}} --------------------------------------------------------------------------
//{{{ includes / predeclarations -----------------------------------------------

// @(#) $Id: ortho.cpp 53 2012-05-23 13:56:41Z nsouchon-dico@altern.org $

#include "ortho.h"
#include "moc_ortho.cpp"

#include "tools.h"
#include "config.h"

//}}} --------------------------------------------------------------------------
//{{{ .Ortho -------------------------------------------------------------------
//}}} --------------------------------------------------------------------------
//{{{ .Ortho (QObject* parent) : -----------------------------------------------

Ortho::Ortho (QObject* parent) :
    QObject (parent)
{
    // initialisations pour dlDistance
    for (int i = 0 ; i != 256 ; i++)
        m_distance[i][0] = i;

    for (int j = 0 ; j != 256 ; j++)
        m_distance[0][j] = j;

    // Table "fr" pour le soundex
    m_soundexCode.insert ('B', '1');
    m_soundexCode.insert ('P', '1');
    m_soundexCode.insert ('C', '2');
    m_soundexCode.insert ('K', '2');
    m_soundexCode.insert ('Q', '2');
    m_soundexCode.insert ('D', '3');
    m_soundexCode.insert ('T', '3');
    m_soundexCode.insert ('L', '4');
    m_soundexCode.insert ('M', '5');
    m_soundexCode.insert ('N', '5');
    m_soundexCode.insert ('R', '6');
    m_soundexCode.insert ('G', '7');
    m_soundexCode.insert ('J', '7');
    m_soundexCode.insert ('X', '8');
    m_soundexCode.insert ('Z', '8');
    m_soundexCode.insert ('S', '8');
    m_soundexCode.insert ('F', '9');
    m_soundexCode.insert ('V', '9');

    QString ced ("Ç");
    m_soundexCode.insert (ced.at (0), '8'); // contournement du fait que 'Ç' n'est pas un QChar

	//	m_convertionTable.insert ("'", "");	// remplacer l'apostrophe par rien
	//	m_convertionTable.insert ("-", "");	// remplacer le tiret par rien
	//	m_convertionTable.insert ("à", "A");
	//	m_convertionTable.insert ("ä", "A");
	//	m_convertionTable.insert ("â", "A");
	//	m_convertionTable.insert ("ä", "A");
	//	m_convertionTable.insert ("é", "E");
	//	m_convertionTable.insert ("è", "E");
	//	m_convertionTable.insert ("ê", "E");
	//	m_convertionTable.insert ("ë", "E");
	//	m_convertionTable.insert ("î", "I");
	//	m_convertionTable.insert ("ï", "I");
	//	m_convertionTable.insert ("ô", "O");
	//	m_convertionTable.insert ("ö", "O");
	//	m_convertionTable.insert ("ù", "U");
	//	m_convertionTable.insert ("û", "U");
	//	m_convertionTable.insert ("ü", "U");
	//	m_convertionTable.insert ("æ", "AE");
	//	m_convertionTable.insert ("œ", "OE");
	//	m_convertionTable.insert ("ç", "C");
	//	m_convertionTable.insert ("ÿ", "Y");
	//	m_convertionTable.insert ("ŷ", "Y");
	//	m_convertionTable.insert ("ã", "A");
	//	m_convertionTable.insert ("ẽ", "E");
	//	m_convertionTable.insert ("ĩ", "Y");
	//	m_convertionTable.insert ("ñ", "N");
	//	m_convertionTable.insert ("õ", "O");
	//	m_convertionTable.insert ("ũ", "U");
	//	m_convertionTable.insert ("ṽ", "V");
	//	m_convertionTable.insert ("ỹ", "Y");
	//	m_convertionTable.insert ("ß", "SS");
	//	m_convertionTable.insert ("ì", "I");
	//	m_convertionTable.insert ("í", "I");
	//	m_convertionTable.insert ("ò", "O");
	//	m_convertionTable.insert ("ó", "O");
	//	m_convertionTable.insert ("á", "A");
	//	m_convertionTable.insert ("á", "A");
	//	m_convertionTable.insert ("í", "I");
	//	m_convertionTable.insert ("ú", "U");

	//	for (char car = 'a' ; car <= 'z' ; car++) {
	//		m_convertionTable.insert (QString (car), (QString (car)).toUpper ());
	//	}



}

//}}} --------------------------------------------------------------------------
//{{{ .~Ortho () ---------------------------------------------------------------

Ortho::~Ortho ()
{
    savePersonalDic ();
    saveTranslateDic ();
}

//}}} --------------------------------------------------------------------------
//{{{ .bool              init () -----------------------------------------------

bool Ortho::init ()
{
    typedef Config::DicDesc DicDesc;

    // configuration de Ortho
    m_config = new Config (this);	// *** lecture de la config
    setLengthMin (m_config->optionLengthMin ());
    setWeirdMax (m_config->optionWeirdMax ());

    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    // this should probably by done in _setCurrentLanguage
    //     loadPersonalDic
    //     loadTranslateDic
    // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

    if ((Config::usedConf == Config::NS) || (Config::usedConf == Config::NS_MERGED))
    {
        _setCurrentLanguage (m_config->optionCurrentLanguage ());
        loadPersonalDic ();
        loadTranslateDic ();
        return (true);
    }

    // détermine le path des dicos
    foreach (const QString& test, m_config->dicsPossiblePaths ()) {
        if (QDir (test).exists ()) {
            m_dicsPath = test;
            break;
        }
    }

    if (m_dicsPath.isEmpty ()) {
        sendMessage (tr ("aucun dictionnaire trouvé !"));
        return false; // Ortho ne peut se lancer
    }

    const QDir& dir (m_dicsPath);
    const QString filter (Config::dicFilter ());

    // détermine les différentes langues dispo
    m_availableLanguages.clear ();

    foreach (const QString& fileName, dir.entryList (QStringList () << filter)) {
        const QFileInfo& info (fileName);
        const QString& lang (info.baseName ());
        m_availableLanguages.insert (lang, m_dicsPath + fileName);
    }
    qDebug () << m_availableLanguages;

    setCurrentLanguage (m_config->optionCurrentLanguage ());
    // charge les dicos et listes annexes
    loadPersonalDic ();
    loadTranslateDic ();

    return true;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              prepareHash (Config::DicDesc & desc) ------------------

//{{{ function documentation ---------------------------------------------------

/*!
 * @brief    prepare a pre-hashed dictionary
 *
 * @param    desc    dictionary description
 */

//}}} --------------------------------------------------------------------------

void Ortho::prepareHash (Config::DicDesc & desc)
{
    QFile inFile (desc.dir + desc.name);
    if (! inFile.open (QIODevice::ReadOnly)) return;

    QTextStream inStream (&inFile);
    inStream.setCodec ("UTF-8");

    QElapsedTimer  timer;
    timer.restart ();

    desc.wordSet = inStream.readAll ().split ('\n', QString::SkipEmptyParts).toSet ();
    desc.wordSet.squeeze ();
    desc.charSet.clear ();
    desc.wordHash.clear ();
    desc.wordHash.reserve (desc.wordSet.count ());

    foreach (const QString & word, desc.wordSet)
    {
        desc.wordHash[sonex (word)] << word;
        foreach (const QChar& car, word)
        {
            desc.charSet << car.toLower () << car.toUpper ();
        }
    }
    qDebug () << "do pre-hash    :" << timer.restart () << "ms";

    QFile outFile (desc.hashed);
    if (! outFile.open (QIODevice::WriteOnly)) return;
    QDataStream outStream (&outFile);
    outStream << desc.charSet << desc.wordSet << desc.wordHash;
    qDebug () << "write pre-hash :" << timer.restart () << "ms";
}

//}}} --------------------------------------------------------------------------
//{{{ .void              _setCurrentLanguage (const QString & lang) ------------

//{{{ function documentation ---------------------------------------------------

/*!
 * @brief    set the current edition language
 *
 *           do nothing if language already set\n
 *           do nothing if there is no dictionary description for the language\n
 *           prepare pre-hashed dictionaries if necessary\n
 *           read pre-hashed dictionaries\n
 *
 * @todo     should verify file opening tests 
 *
 * @param    lang    edition language to set
 */

//}}} --------------------------------------------------------------------------

void Ortho::_setCurrentLanguage (const QString & lang)
{
    typedef Config::DicDesc DicDesc;

    if (currentLanguage () == lang) return;

    QHash<QString,QList<DicDesc> > allDescs = DicDesc::list ();
    if (! allDescs.keys ().contains (lang))
    {
        sendMessage (tr ("no dictionary found !"));
        return;
    }
    QList<DicDesc> descs = allDescs[lang];

    qDebug () << Q_FUNC_INFO;

    QElapsedTimer  timer;
    timer.restart ();

    for (int i = 0; i < descs.count (); i++)
    {
        DicDesc & desc = descs[i];
        QFile     hash (desc.hashed);
        if (desc.hashNeedUpdate ())
        {
            prepareHash (desc);
        }
    }
    qDebug () << "pre-hashing    :" << timer.restart () << "ms";

    int rmDup = 0;
    m_charSet .clear ();
    m_wordSet .clear ();
    m_wordHash.clear ();
    for (int i = 0; i < descs.count (); i++)
    {
        DicDesc & desc = descs[i];

        if (! desc.wordSet.count ())
        {
            QFile         file (desc.hashed);
            QDataStream   stream (&file);

            file.open (QIODevice::ReadOnly);
            stream >> desc.charSet >> desc.wordSet >> desc.wordHash;
        }

        if (! i)
        {
            m_charSet  = desc.charSet;
            m_wordSet  = desc.wordSet;
            m_wordHash = desc.wordHash;
        }
        else
        {
            m_charSet.unite (desc.charSet);
            m_wordSet.unite (desc.wordSet);
            foreach (QString k, desc.wordHash.keys ())
            {
                QStringList & v = m_wordHash[k];
                v.append (desc.wordHash[k]);
                if (rmDup == 1) v.removeDuplicates ();
            }
        }
        if (rmDup == 2) foreach (QString k, m_wordHash.keys ())
        {
            m_wordHash[k].removeDuplicates ();
        }
    }
    qDebug () << "read pre-hash  :" << timer.restart () << "ms";

    sendMessage (tr ("dictionnaire(s) <b>%1</b> correctement chargé(s) : contient(contiennent) %2 mots.")
            .arg (lang)
            .arg (m_wordSet.size ()));

    m_currentLanguage = lang;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              setCurrentLanguage (const QString & lang) -------------

void Ortho::setCurrentLanguage (const QString& lang)
{
    if (currentLanguage () == lang) return;

    const bool ok = loadDic (lang);
    if (!ok)
        sendMessage (tr ("le dictionnaire %1 ne peut être chargé.")
                .arg (lang));
    else {
        sendMessage (tr ("le dictionnaire <b>%1</b> a été correctement chargé et contient %2 mots.")
                .arg (lang)
                .arg (m_wordSet.size ()));
    }

    m_currentLanguage = lang;
}

//}}} --------------------------------------------------------------------------
//{{{ .bool              loadDic (const QString & lang) ------------------------

bool Ortho::loadDic (const QString& lang)
{
    if (!availableLanguages ().contains (lang)) return false;

    const QString& fileName (m_availableLanguages.value (lang));
    qDebug () << "load dic" << fileName;
    QFile file (fileName);  // nom du fichier

    if (!file.open (QIODevice::ReadOnly | QIODevice::Text)) {
        sendMessage (tr ("impossible d'ouvrir le dictionnaire %1").arg (lang));
        return false;
    }

    // charge le dico
    QApplication::setOverrideCursor (QCursor (Qt::WaitCursor));

    QTextStream in (&file);
    in.setCodec ("UTF-8");
    m_wordSet = in.readAll ().split ('\n', QString::SkipEmptyParts).toSet ();
    m_wordSet.squeeze ();

    QApplication::restoreOverrideCursor ();

    buildHashs ();

    return true;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              buildHashs () -----------------------------------------

void Ortho::buildHashs ()
{
    // noter la liste des différents caractères que contient le dico,
    // préparer la table de hachage avec sonex

    CHRONO_START;
    QApplication::setOverrideCursor (QCursor (Qt::WaitCursor));
    m_charSet.clear ();
    m_wordHash.clear ();
    m_wordHash.reserve (m_wordSet.count ());

    foreach (const QString& word, m_wordSet) {
        m_wordHash[sonex (word)] << word;
        foreach (const QChar& car, word) {
            if (! m_charSet.contains (car)) {
                m_charSet << car.toLower () << car.toUpper ();
            }
        }
    }

    m_charSet.squeeze ();
    m_wordHash.squeeze ();

    QApplication::restoreOverrideCursor ();

    CHRONO_END;
}

//}}} --------------------------------------------------------------------------
//{{{ .QStringList       suggestsFor (const QString & target) ------------------

QStringList Ortho::suggestsFor (const QString& target)
{
    // on suppose que le mot n'est PAS dans les dicos

    if (target.length () < m_lengthMin) return QStringList ();

    QStringList result (decomp (target));

//        if (! result.isEmpty ()) {
//            return result;
//        }

    const int distMax = distanceMax (target.length ()); // distance "raisonnable".

    QMap<int, QString> map;

    const bool firstCap = isFirstCap (target);
    const bool allCap = isAllCap (target);
    const QString& lowerTarget (target.toLower ());

    foreach (const QString& word, m_wordSet) {
        if (word.at (0).toLower () == target.at (0).toLower () || ordered (word) == ordered (target))
        {
            const int dist = dlDistance (lowerTarget, word, true, distMax);   // damerau = true
            if (dist != -1)
            {
                map.insertMulti (dist, firstCap ? toFirstCap (word) : allCap ? word.toUpper () : word);
            }
        }
    }

    if (!map.isEmpty ()) {
        const int min = map.keys ().at (0);
        QStringList result2 (map.values (min));
        result2.sort ();
        result += result2;
    }

    result += m_wordHash.value (sonex (target));

    result.removeDuplicates ();
//    result.sort ();

    return result;
}

//}}} --------------------------------------------------------------------------
//{{{ .QStringList       unknownWords (const QString & text) -------------------

QStringList Ortho::unknownWords (const QString& text)
{
    QString workText;

    foreach (const QChar& car, text) {
        if (car.isSpace () || car.isLetterOrNumber ()/*m_charSet.contains (car)*/)
            workText += car;
    }

    const QStringList words (workText.simplified ().split (QRegExp ("\\b"), QString::SkipEmptyParts)); // liste des mots

    QSet<QString> result;

    foreach (const QString& word, words) {
        if (isUnknown (word)) {
            result << word;
        }
    }

    return result.toList ();
}

//}}} --------------------------------------------------------------------------
//{{{ .const QStringList decomp (const QString & word) -------------------------

const QStringList Ortho::decomp (const QString &word)
{
    // word n'existe pas dans le dico
    static const QString format ("%1 %2");

    QStringList result;

    const int wordLen = word.length ();
    if (wordLen <= 2 * m_lengthMin) return result;

    foreach (const QString& possibleBegin, m_wordSet) {
        const int beginLen = possibleBegin.length ();

        if (wordLen > beginLen && word.startsWith (possibleBegin)) {
            const QString& end (word.mid (beginLen));
            if (dicContains (end)) {
                result << format.arg (possibleBegin).arg (end);
            }
        }
    }

    return result;
}

//}}} --------------------------------------------------------------------------
//{{{ .int               weirdCount (const QString & word) ---------------------

int Ortho::weirdCount (const QString &word)
{
    int result = 0;

    foreach (const QChar& car, word) {
        if (! m_charSet.contains (car)) {
            ++result;
        }
    }

    return result;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              setDistanceMax (const int distance) -------------------

void Ortho::setDistanceMax (const int distance)
{
    m_distanceMax = distance;
}

//}}} --------------------------------------------------------------------------
//{{{ .int               distanceMax (const int len) ---------------------------

int Ortho::distanceMax (const int len)
{
    if (m_distanceMax) return m_distanceMax;
    if (len < 3) return 1;
    if (len < 6) return 2;
    return 3;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              addLineToPersonalDic (const QString & word) -----------

void Ortho::addLineToPersonalDic (const QString &word)
{
    if (word.isEmpty ()) return;
    if (m_personalDic.contains (word)) return;
    m_personalDic << word;
    m_personalDic.removeDuplicates ();
    m_wordSet << word;
    sendMessage (tr ("ajout de <i>%1</i> au dictionnaire personnel.").arg (word));
    emit personalDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              removeLineFromPersonalDic (const QString & word) ------

void Ortho::removeLineFromPersonalDic (const QString &word)
{
    if (word.isEmpty ()) return;
    if (!m_personalDic.contains (word)) return;
    m_personalDic.removeOne (word);
    m_wordSet.remove (word);
    sendMessage (tr ("retrait de <i>%1</i> du dictionnaire personnel.").arg (word));
    emit personalDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              loadPersonalDic () ------------------------------------

void Ortho::loadPersonalDic ()
{
    QFile file (Config::personalDicPath ());
    file.open (QIODevice::ReadOnly | QIODevice::Text);
    QTextStream in (&file);
    in.setCodec ("UTF-8");
    m_personalDic.clear ();
    while (!in.atEnd ()) {
        const QString& word (in.readLine ());
        m_personalDic << word;
    }
    m_personalDic.removeDuplicates ();
    m_wordSet += m_personalDic.toSet ();

    sendMessage (tr ("le dictionnaire personnel a été chargé : %1 mots").arg (m_personalDic.size ()));
    emit personalDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              savePersonalDic () ------------------------------------

void Ortho::savePersonalDic ()
{
    QFile file (Config::personalDicPath ());
    file.open (QIODevice::WriteOnly | QIODevice::Text);
    QTextStream out (&file);
    out.setCodec ("UTF-8");
    const QString& tmp = m_personalDic.join ("\n");
    out << tmp;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              mergeToPersonalDic (const QString & fileName) ---------

void Ortho::mergeToPersonalDic (const QString& fileName)
{
    QFile file (fileName);
    file.open (QIODevice::ReadOnly | QIODevice::Text);
    QTextStream in (&file);
    in.setCodec ("UTF-8");
    const QStringList& tmp (in.readAll ().split ("\n", QString::SkipEmptyParts));
    m_personalDic += tmp;
    m_personalDic.removeDuplicates ();
    sendMessage (tr ("le dictionnaire personnel a été enrichi du contenu de <b>%1</b>.").arg (fileName));
    emit personalDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              clearPersonalDic () -----------------------------------

void Ortho::clearPersonalDic ()
{
    m_personalDic.clear ();
    savePersonalDic ();
    sendMessage (tr ("le dictionnaire personnel a été effacé."));
    emit personalDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              loadTranslateDic () -----------------------------------

void Ortho::loadTranslateDic ()
{
    QSettings settings (Config::translateDicPath (), QSettings::IniFormat);
    m_translateDic = settings.value (QString ("Translations"), QHash<QString, QVariant> ()).toHash ();
    sendMessage (tr ("la liste des remplacements automatiques a été chargée."));
    emit translateDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              addLineToTranslateDic (const QString & bad, const QString & good) -

void Ortho::addLineToTranslateDic (const QString& bad, const QString& good)
{
    if (bad.isEmpty () || good.isEmpty ()) return;
    if (!dicContains (good))
    {
        addLineToPersonalDic (good);
    }
    m_translateDic.insert (bad, good);
    sendMessage (tr ("toujours remplacer <i>%1</i> par <i>%2</i>.").arg (bad).arg (good));
    emit translateDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              saveTranslateDic () -----------------------------------

void Ortho::saveTranslateDic ()
{
    QSettings settings (Config::translateDicPath (), QSettings::IniFormat);
    settings.setValue (QString ("Translations"), m_translateDic);
}

//}}} --------------------------------------------------------------------------
//{{{ .void              clearTranslateDic () ----------------------------------

void Ortho::clearTranslateDic ()
{
    m_translateDic.clear ();
    saveTranslateDic ();
    sendMessage (tr ("la liste des remplacements automatiques a été effacée."));
    emit translateDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .void              removeLineFromTranslateDic (const QString & line) -----

void Ortho::removeLineFromTranslateDic (const QString& line) // en fait bad + separator () + good
{
    QString bad = line.left (line.indexOf (separator ()));
    m_translateDic.remove (bad);
    sendMessage (tr ("<i>%1</i> a été effacé de la liste des remplacements automatiques.").arg (bad));
    emit translateDicHasChanged ();
}

//}}} --------------------------------------------------------------------------
//{{{ .QString           translate (const QString & text) ----------------------

QString Ortho::translate (const QString& text)
{
    QString result (text);

    foreach (const QString& bad, m_translateDic.keys ())
    {
        if (text.contains (bad))
        {
            QString good = m_translateDic.value (bad).toString ();
            result.replace (bad, good);
            sendMessage (tr ("<i>%1</i> a été remplacé automatiquement par <i>%2</i>").arg (bad).arg (good));
        }
    }

    return result;
}

//}}} --------------------------------------------------------------------------
//{{{ .QString           autoSpelling (const QString & text) -------------------

QString Ortho::autoSpelling (const QString& text)
{
    QString result (translate (text));

    m_autoSpellingStop = false;
    const QStringList& unknown (unknownWords (result));

    const int count = unknown.size ();

    if (count == 0) return result;
    int advance = 0;
    emit autoSpellingCount (count);

    foreach (const QString& bad, unknown) {
        const QStringList& sugg (suggestsFor (bad));
        ++advance;

        emit autoSpellingAdvance (advance);
        QApplication::processEvents ();
        if (m_autoSpellingStop) {
            emit autoSpellingAdvance (count);
            QApplication::processEvents ();
            return result;
        }
        if (sugg.count () == 1) {
            const QString& good (sugg.at (0));
            result.replace (bad, good);
            sendMessage (tr ("<i>%1</i> a été corrigé en : <i>%2</i>").arg (bad).arg (good));
        }
    }

    return result;
}

//}}} --------------------------------------------------------------------------
//{{{ .void              sendMessage (const QString & msg) ---------------------

void Ortho::sendMessage (const QString &msg)
{
    QString messageTxt (QString ("Ortho : %1").arg (msg));
    emit message (messageTxt);
    QApplication::processEvents ();
}

//}}} --------------------------------------------------------------------------
//{{{ .QStringList       translateDicAsList () ---------------------------------

QStringList Ortho::translateDicAsList ()
{
    QStringList result;

    foreach (const QString& bad, m_translateDic.keys ()) {
        const QString& good = m_translateDic.value (bad).toString ();
        result << bad % separator () % good;
    }
    return result;
}

//}}} --------------------------------------------------------------------------
//{{{ .int               dlDistance (const QString & s1, const QString & s2, const bool dmr, const int md) -

int Ortho::dlDistance (const QString &str1,
                       const QString &str2,
                       const bool damerau,
                       const int maxDiff)
{
    // cf. http://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein

    const int lim1 = str1.length () + 1;
    const int lim2 = str2.length () + 1;

    if (abs (lim1 - lim2) > maxDiff) return -1;

    // **************** calcul de la distance ****************

    int (*d)[256] = m_distance;

    if (damerau) {
        // si damerau == true (dans mcroises.conf au démarrage de l'appli) on teste les transpositions

        for (int i = 1 ; Q_LIKELY (i < lim1) ; i++) {
            int minOfLine = 0xff;

            for (int j = 1 ;  Q_LIKELY (j < lim2) ; j++) {
                const int cost = (str1.at (i-1) == str2.at (j-1)) ? 0 : 1;
                int best;
                if (Q_LIKELY (i > 1 && j > 1)
                        && str1.at (i-1) == str2.at (j-2)
                        && str1.at (i-2) == str2.at (j-1)) {
                    // damerau = tester les transpositions avec i >= 2 et j >= 2
                    best = Tools::min (d[i-1][j] + 1,			// suppression
                                       d[i][j-1] + 1,			// insertion
                                       d[i-1][j-1] + cost,		// substitution
                                       d[i-2][j-2] + cost);		// transposition
                }
                else {
                    best = Tools::min (d[i-1][j] + 1,			// suppression
                                       d[i][j-1] + 1,			// insertion
                                       d[i-1][j-1] + cost);		// substitution

                }

                d[i][j] = best;
                if (minOfLine > best) minOfLine = best;
            }
            if (minOfLine > maxDiff) return -1;
        }
    }
    else {
        for (int i = 1 ; i < lim1 ; ++i) {
            int minOfLine = 0xff;

            for (int j = 1 ; j < lim2 ; ++j) {

                const int best = Tools::min (d[i-1][j] + 1,		// suppression
                                             d[i][j-1] + 1,		// insertion
                                             d[i-1][j-1]		// substitution
                                             + (str1.at (i-1) == str2.at (j-1)) ? 0 : 1);
                d[i][j] = best;
                if (minOfLine > best) minOfLine = best;
            }
            if (minOfLine > maxDiff) return -1;
        }
    }

    int result = d[lim1-1][lim2-1];

    return (result > maxDiff ? -1 : result);
}

//}}} --------------------------------------------------------------------------
//{{{ .QString           soundex (const QString & word) const ------------------

// Algo SOUNDEX :
//1. mettre le mot en majuscule, eliminer les ponctuations
//2. garder la premiere lettre du mot
//3. supprimer les occurences de: A E I O U H W Y
//4. faire les changements suivants:
// Regles de conversion pour le francais:
//	→               →             →
//	BP           1   L            4   GJ    7
//							                                →             →
//	 →        MN           5   XZS   8
//							        CKQ          2
//							                →               →             →
//							        DT           3   R            6   FV    9

//5. si deux lettres adjacentes dans la chaîne de depart ont le
//meme code, ne garder que la premiere de ces lettres
// (elimination des doublons)
//6. retourner les 4 premiers caracteres (completer par des
//zeros le cas echeant)

QString Ortho::soundex (const QString &word) const
{
    static const QString consonants ("BCÇDFGJKLMNPQRSTVXZ");
    static const QString soundexFormat  ("%1%20000");

    QString result;
    QChar lastCar;

    foreach (const QChar& car, (word.mid (1)).toUpper ()) {
        if (consonants.contains (car)) {
            const QChar& code (soundexCode (car));
            if (lastCar != code) {
                lastCar = code;
                result += code;
                if (result.length () == 3) break;
            }
        }
    }

    return (soundexFormat.arg (word.at (0).toUpper ()).arg (result)) .left (4);
}

//}}} --------------------------------------------------------------------------
//{{{ .QString           sonex (const QString & word) const --------------------

QString Ortho::sonex (const QString& word) const
{
    static const unsigned char isConsonne  = 0x07;
    static const unsigned char isH         = 0x01;
    static const unsigned char isM         = 0x02;
    static const unsigned char isL         = 0x04;
    static const unsigned char isS         = 0x06;  // pour gérer les consonnes
                                                    // explosives directement
                                                    // suivies d'une sifflante

    static const unsigned char isVoyelle   = 0xF8;
    static const unsigned char isSlender   = 0x38;
    static const unsigned char isI         = 0x08;
    static const unsigned char isY         = 0x10;
    static const unsigned char isE         = 0x20;
    static const unsigned char isBroad     = 0xC0;
    static const unsigned char isU         = 0x40;
    static const unsigned char isO         = 0x80;

    static const unsigned char isLastE = isE | isH; // l'avant dernier e se prononce 'é
    static const unsigned char isW     = isO | isH; // pour le cas particulier du 'ow'
    static const unsigned char isEx    = isE | isS;
    static const unsigned char isOn    = isO | isM;
    static const unsigned char isIn    = isI | isM;
    static const unsigned char isN     = isM | isH;

    QString son;

    unsigned char info_n0 (0), info_n1 (isL), info_n2 (0); // permettra de gérer
                                                        // les graphies finales
                                                        // de type 'ail' ou 'euil'...
    QString code;
    bool conversionOfTion = false;

    int len = word.length ();
    int last = len - 1;
    int charCode;

    for (int i = len - 1; i > -1; --i)
    {
        charCode = word.at (i).unicode ();
        switch (charCode)
        {
            case 0x61:  // a
            case 0x41:  // A
                info_n0 = isBroad;
                switch (info_n1)
                {
                    case isO:
                    case isU:
                        break;
                    case isI:
                    case isIn:
                        pushCode ("I", code);
                        break;
                    case isOn:
                    case isM:
                    case isN:
                    case isY:
                        popCode (code);
                    default:
                        pushCode ("A", code);
                        break;
                }
                break;
            case 0xe0:  // a accent grave
            case 0xc0:  // A accent grave
            case 0xe2:  // a circonflexe
            case 0xc2:  // A circonflexe
                info_n0 = isBroad;
                pushCode ("A", code);
                break;
            case 0xe6:  // e dans l'a
            case 0xc6:  // E dans l'a
                info_n0 = isBroad;
                pushCode ("I", code);
                break;
            case 0x62:  // b
            case 0x42:  // B
                info_n0 = isConsonne;
                pushCode ((info_n1 == isS) ? "": "B", code);
                break;
            case 0x63:  // c
            case 0x43:  // C
                info_n0 = isConsonne;
                switch (info_n1)
                {
                    case isSlender:
                    case isI:
                    case isY:
                    case isIn:
                    case isE:
                        info_n0 = isS;
                        pushCode ("S", code);
                        break;
                    case isH:
                        pushCode ("J", code);
                        info_n0 = isH;
                        break;
                    case isS:
                        break;
                    default:
                        pushCode ("K", code);
                        break;
                }
                break;
            case 0xe7:  // c cédille
            case 0xc7:  // C cédille
                info_n0 = isS;
                pushCode ("S", code);
                break;
            case 0x64:  // d
            case 0x44:  // D
                if (i == last)
                    info_n0 = isLastE;
                else
                {
                    info_n0 = isConsonne;
                    pushCode ((info_n1 == isS) ? "": "D", code);
                }
                break;
            case 0x65:  // e
            case 0x45:  // E
                if (i != last)
                {
                    switch (info_n1)
                    {
                        case isO:
                        case isE:
                            popCode (code);
                        case isLastE:
                        case isEx:
                            pushCode ("I", code);
                            break;
                        case isM:
                        case isN:
                            if (! (info_n2 & isVoyelle))
                                pushCode ("A", code);
                            break;
                        case isU:
                            popCode (code);
                            if (Q_UNLIKELY (info_n2 == isY))
                                popCode (code);
                            pushCode ("E", code);
                            break;
                        default:
                            if (info_n1 & isConsonne && info_n2 & isConsonne)
                                pushCode ("I", code);
                            break;
                    }
                }
                info_n0 = isE;
                break;
            case 0xe8:  // e accent grave
            case 0xc8:  // E accent grave
            case 0xe9:  // e accent aigu
            case 0xc9:  // E accent aigu
            case 0xea:  // e circonflexe
            case 0xca:  // E circonflexe
            case 0xeb:  // e tréma
            case 0xcb:  // E tréma
                info_n0 = isSlender;
                pushCode ("I", code);
                break;
            case 0x66:  // f
            case 0x46:  // F
            case 0x76:  // v
            case 0x56:  // V
                info_n0 = isConsonne;
                pushCode ("F", code);
                break;
            case 0x77:  // w
            case 0x57:  // W
                info_n0 = isW;
                pushCode ("F", code);
                break;
            case 0x67:  // g
            case 0x47:  // G
                info_n0 = isConsonne;
                switch (info_n1)
                {
                    case isM:
                    case isN:
                        pushCode ("M", code);
                        break;
                    case isSlender:
                    case isI:
                    case isIn:
                    case isY:
                    case isE:
                        pushCode ("J", code);
                        break;
                    case isS:
                        break;
                    case isU:
                        if (Q_UNLIKELY (info_n2 & isSlender))
                            popCode (code);
                    default:
                        pushCode ("K", code);
                        break;
                }
                break;
            case 0x68:  // h
            case 0x48:  // H
                info_n0 = isH;
                break;
            case 0x69:  // i
            case 0x49:  // I
            case 0xee:  // i circonflexe
            case 0xce:  // I circonflexe
                info_n0 = isI;
                switch (info_n1)
                {
                    case isM:
                    case isN:
                        pushCode ("I", code);
                        info_n0 = isIn;
                        break;
                    case isL: // isLL
                        if (info_n2 == isL)
                        {
                            popCode (son);
                            pushCode ("Y", code);
                            info_n0 = isY;
                        }
                        pushCode ("I", code);
                        break;
                    case isE:
                        if (info_n2 == isN || info_n2 == isM)
                            popCode (code);
                    default:
                        pushCode ("I", code);
                        break;
                }
                break;
            case 0xef:  // i tréma
            case 0xcf:  // I tréma
                info_n0 = isSlender;
                pushCode ("I", code);
                break;
            case 0x6a:  // j
            case 0x4a:  // J
                info_n0 = isConsonne;
                pushCode ("J", code);
                break;
            case 0x6b:  // k
            case 0x4b:  // K
                info_n0 = isConsonne;
                pushCode ((info_n1 == isN) ? "" : "K", code);
                break;
            case 0x6c:  // l
            case 0x4c:  // L
                info_n0 = isL;
                pushCode ("L", code);
                break;
            case 0x6d:  // m
            case 0x4d:  // M
                info_n0 = isM;
                if (info_n1 & isVoyelle)
                {
                    pushCode ("M", code);
                    info_n0 = isConsonne;
                }
                break;
            case 0x6e:  // n
            case 0x4e:  // N
                info_n0 = isN;
                if (info_n1 & isVoyelle)
                    pushCode ("M", code);
                break;
            case 0x6f:  // o
            case 0x4f:  // O
                info_n0 = isO;
                switch (info_n1)
                {
                    case isIn:
                        info_n0 = isBroad;
                        pushCode ("I", code);
                        break;
                    case isE:
                        info_n0 = isBroad;
                        if (info_n2 == isY)
                        {
                            popCode (code);
                            pushCode ("E", code);
                        }
                        break;
                    case isI:
                        info_n0 = isBroad;
                        pushCode ("A", code);
                        break;
                    case isM:
                    case isN:
                        info_n0 = isOn;
                        pushCode ("O", code);
                        break;
                    case isW:
                        info_n0 = isBroad;
                        popCode (code);
                        pushCode ("O", code);
                        break;
                    default:
                        pushCode ("O", code);
                        break;
                }
                break;
            case 0xf4:  // o circonflexe
            case 0xd4:  // O circonflexe
            case 0xf6:  // o tréma
            case 0xd6:  // O tréma
                info_n0 = isBroad;
                pushCode ("O", code);
                break;
            case 0x153: // e dans l'o
            case 0x152: // E dans l'o
                info_n0 = isBroad;
                if (info_n1 == isU)
                {
                    if (info_n2 == isY)
                        popCode (code);
                    pushCode ("E", code);
                }
                else if (info_n1 == isY)
                {
                    popCode (code);
                    pushCode ("E", code);
                }
                else
                    pushCode ("I", code);
                break;
            case 0x70:  // p
            case 0x50:  // P
                if (i != last)
                {
                    switch (info_n1)
                    {
                        case isH:
                            pushCode ("F", code);
                            break;
                        case isS:
                            break;
                        default:
                            pushCode (info_n1 == isS ? "" : "B", code);
                            break;
                    }
                }
                info_n0 = isConsonne;
                break;
            case 0x71:  // q
            case 0x51:  // Q
                info_n0 = isConsonne;
                switch (info_n1)
                {
                    case isS:
                        break;
                    case isU:
                        if (Q_UNLIKELY (info_n2 & isConsonne))
                        {
                            if (Q_UNLIKELY (info_n2 == isM || info_n2 == isN))
                                pushCode ("M", code);
                            pushCode ("O", code);
                        }
                        else
                            popCode (code);
                    default:
                        pushCode ("K", code);
                        break;
                }
                break;
            case 0x72:  // r
            case 0x52:  // R
                info_n0 = isConsonne;
                pushCode ("R", code);
                break;
            case 0x73:  // s
            case 0x53:  // S
                if (i != last)
                {
                    switch (info_n1)
                    {
                        case isH:
                            pushCode ("J", code);
                            break;
                        default:
                            pushCode ("S", code);
                            break;
                    }
                }
                info_n0 = isS;
                break;
            case 0x74:  // t
            case 0x54:  // T
                if (i == last)
                    info_n0 = isLastE;
                else
                {
                    info_n0 = isConsonne;
                    pushCode ((info_n1 == isS) ? "": "D", code);
                }
                break;
            case 0x75:  // u
            case 0x55:  // U
            case 0xf9:  // u accent grave
            case 0xd9:  // U accent grave
                info_n0 = isU;
                if (info_n1 == isM || info_n1 == isN)
                    pushCode ("I", code);
                else if (Q_UNLIKELY (info_n1 == isE && info_n2 == isY))
                {
                    popCode (code);
                    pushCode ("E", code);
                }
                else
                    pushCode ("O", code);
                break;
            case 0xfb:  // u circonflexe
            case 0xdb:  // U circonflexe
            case 0xfc:  // u tréma
            case 0xdc:  // U tréma
                info_n0 = isBroad;
                    pushCode ("O", code);
                break;
            case 0x78:  // x
            case 0x58:  // X
                info_n0 = isEx;
                if (Q_LIKELY (i != last))
                    pushCode ("S", code);
                break;
            case 0x79:  // y
            case 0x59:  // y
                info_n0 = isI;
                if (i == last)
                    pushCode ("I", code);
                else
                {
                    if (info_n1 & isConsonne)
                        pushCode ("I", code);
                    else
                        pushCode ("Y", code);
                }
                break;
            case 0xff:  // y tréma
            case 0x178: // Y tréma
                info_n0 = isSlender;
                pushCode ("I", code);
                break;
            case 0x7a:  // z
            case 0x5a:  // Z
                if (i == last)
                    info_n0 = isLastE;
                else
                {
                    info_n0 = isS;
                    pushCode ("S", code);
                }
            break;
            default:
                break;
        }

        // on gère le cas très spécial du 'tion' prononcé 'sion'
        // comme info_n2 sera remplacé à la fin, on l'utilise
        if (Q_UNLIKELY (info_n2 == isOn))
        {
            info_n2 = (charCode & 0x74 /* code hexa pour le 'T' */);
            if (Q_UNLIKELY (info_n2 == 0x74 && info_n1 == isI))
                conversionOfTion = true;
        }
        if (Q_UNLIKELY (conversionOfTion))
        {
            info_n2 = Q_UNLIKELY (charCode < 128) ? (charCode & 0x54) : 0;
                                                    /* code hexa pour le 'T' */
            if (Q_LIKELY (info_n2 != 0x54))
            {
                son.replace (0, 1, "S");
                if (!code.isEmpty ())
                {
                    switch (code.right (1).at (0).unicode ())
                    {
                        case 0x42:  // B
                        case 0x44:  // D
                        case 0x4b:  // K
                            code.chop (1);
                        default:
                            break;
                    }
                }
                conversionOfTion = false;
            }
            else
                conversionOfTion = (info_n1 == isI);
        }

        // On insère le code dans le sonex
        // quand on vient de gérer un son consonnantique
        // si l'on est arrivé au premier caractère
        if (info_n0 & isConsonne)
        {
            if (! (info_n0 & isVoyelle))
            {
                pushCode (code, son);
                code.clear ();
            }
        }
        if (i == 0)
        {
            pushCode (code, son);
            code.clear ();
        }

        // on décale les infos
        qSwap (info_n1, info_n2);
        qSwap (info_n0, info_n1);
    }

    return son;
}

//}}} --------------------------------------------------------------------------

